package 动态规划;

// 问题：从顶部到底部的最小路径和
// 自顶向下
// 状态定义：从(0,0)到(i,j)的最小路径和
// 状态转移方程：F(i,j)：Math.min(F(i-1,j),F(i-1,j-1)) + array[i][j]
//            (j == 0 || j == i) : F(i,j)
//                              j == 0: F(i-1,0) + array[i][0]
//                              j == i: F(i-1,j-1) + array[i][j]
// 状态初始化：F(0,0) = array[0][0]
// 返回结果：Math.min(F(row-1,j)...)
public class NC_CC31_三角形 {
    public int minimumTotal1(int[][] triangle) {
        if(triangle.length == 0) {
            return 0;
        }
        int row = triangle.length;
        int col = triangle[0].length;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j <= i; j++) {
                if(j == 0) triangle[i][j] = triangle[i-1][j] + triangle[i][j];
                else if(j == i) triangle[i][j] = triangle[i-1][j-1] + triangle[i][j];
                else {
                    triangle[i][j] = Math.min(triangle[i-1][j-1],triangle[i][j]) + triangle[i][j];
                }
            }
        }
        int minSum = triangle[row-1][0];
        for (int k = 1; k < col; k++) {
            minSum = Math.min(minSum, triangle[row-1][k]);
        }
        return minSum;
    }

    // 自底向上
    // 状态F(i,j): 从(i,j)到达最后一行的最小路径和
    // 状态转移方程：
    //      F(i,j): min(F(i+1,j),F(i+1, j+1)) + array[i][j]
    // 初始状态：
    //      F(row - 1) = array[row-1][j]
    // 返回结果：
    //      F(0,0)
    public int minimumTotal2(int[][] triangle) {
        int row = triangle.length;
        for (int i = row-2; i >= 0 ; i--) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] = Math.min(triangle[i+1][j+1],triangle[i+1][j]) + triangle[i][j];
            }
        }
        return triangle[0][0];
    }
}
